The term “rays tracing” describes a technique for synthesizing photorealistic images by identifying all light paths that connect light sources with cameras and summing up these contributions. The simulation traces rays along the line of sight to determine visibility, and traces rays from the light sources in order to determine illumination.
Ray tracing has become mainstream in motion pictures and other applications. However, current ray tracing techniques suffer from a number of known limitations and weaknesses, including numerical problems, limited capabilities to process dynamic scenes, slow setup of acceleration data structures, and large memory footprints. Thus, current ray tracing techniques lack the capability to deal efficiently with fully animated scenes, such as wind blowing through a forest or a person's hair. Overcoming the limitations of current ray tracing systems would also enable the rendering of, for example, higher quality motion blur in movie productions.
Current attempts to improve the performance of ray tracing systems have fallen short for a number of reasons. For example, current real-time ray tracing systems generally use 3D-trees as their acceleration structure, which are based on axis-aligned binary space partitions. Because the main focus of these systems is on rendering static scenes, they typically fail to address the significant amount of setup time required to construct the required data structures in connection with fully animated scenes. Along these lines, one manufacturer has improved real-time ray tracing by building efficient 3D-trees and developing an algorithm able to shorten the time needed to traverse the tree. However, it can be shown that the expected memory requirement for the system increases quadratically with an increase in the number of objects to be ray-traced.
Another manufacturer has designed a ray tracing integrated circuit that uses bounding volume hierarchies to improve system performance. However, it has been found that the architecture's performance breaks down if too many incoherent secondary rays are traced.
In addition, attempts have made to improve system performance by implementing 3D-tree traversal algorithms using field-programmable gate arrays (FPGAs). The main increase in processing speed in these systems is obtained by tracing bundles of coherent rays and exploiting the capability of FPGAs to perform rapid hardwired computations. The construction of acceleration structures has not yet been implemented in hardware. The FPGA implementations typically use floating point techniques at reduced precision.
More particularly, ray tracing is a basic technique at the core of many simulation algorithms. It therefore needs to be well accelerated, which often is achieved by implicitly or explicitly constructing a spatial hierarchy. This hierarchy is traversed to efficiently exclude large parts of the scene from being tested for intersection with rays thus making ray tracing efficient.
As will be discussed below, in the present invention, we set forth at least two improvements that are beneficial to that process:
(1) During the construction of the hierarchy usually suitable planes must be found in order to partition space or objects. The more tight intersections of axis-aligned bounding boxes and objects can be determined, the more efficient partitions can be chosen. For the case of triangles under linear motion we introduce an algorithm that computes the minimal axis-aligned bounding box when intersecting all points touched by the linearly moving triangle with a given axis-aligned bounding box. Although approximate tests perform faster than our exact solution, the computational cost is easily amortized as it results in more shallow hierarchies that enable faster ray tracing and reduced memory consumption.
(2) Given a set of rays that can be bounded by a shaft, there is then introduced a may bundle traversal algorithm that traverses acceleration hierarchies at the cost of only one ray.